#include <iostream>
#include <fstream>
#include "Vertex.h"
#include "Line.h"
#include "Edge.h"
#include "Bisector.h"
using namespace std;

#define MAX_NUM_OF_VERTECIES 100

int Partition(int low,int high,Vertex sites[])
{ 
	int i;
	Vertex high_vac, low_vac, pivot/*,itr*/;
	pivot = sites[low];
	
	while(high > low)
	{
		high_vac = sites[high];

		while(pivot < high_vac)
		{
			if(high <= low) break;
			high--;
			high_vac = sites[high];
		}

		sites[low] = high_vac;
		low_vac = sites[low];

		while(pivot > low_vac)
		{
			if(high <= low) break;
			low++;
			low_vac = sites[low];
		}
		sites[high] = low_vac;
	}
	
	sites[low] = pivot;
	return low;
}

void QuickSort(int low,int high,Vertex sites[])
{
	int Piv_index,i;
	if(low < high)
	{
		Piv_index = Partition(low,high,sites);
		QuickSort(low,Piv_index-1,sites);
		QuickSort(Piv_index+1,high,sites);
	}
}

Line GetLineEquation (Vertex p1 , Vertex p2)
{
	Line line;
	if((p2.x - p1.x) == 0 || (p2.y - p1.y) == 0)
		line.slope = 0;
	else
	{
		line.slope = (p2.y - p1.y) / (p2.x - p1.x);
		line.b = p2.y - (line.slope * p2.x);
	}
	return line;
}

Line GetLineNormal (Edge edge)
{
	Line Normal;
	Vertex bisectionPoint;
	if(edge.line.slope == 0 && edge.startPoint.x == edge.endPoint.x)
	{
		Normal.slope = 0;
		bisectionPoint.x = edge.startPoint.x;
		bisectionPoint.y = (edge.endPoint.y + edge.startPoint.y)/2;
		Normal.y = bisectionPoint.y;
		Normal.x = -100000000;
	}

	else if(edge.line.slope == 0 && edge.startPoint.y == edge.endPoint.y)
	{
		Normal.slope = 0;
		bisectionPoint.y = edge.startPoint.y;
		bisectionPoint.x = (edge.endPoint.x + edge.startPoint.x)/2;
		Normal.x = bisectionPoint.x;
		Normal.y = -100000000;
	}

	else
	{
		Normal.slope = -1 * (1 / edge.line.slope);

		bisectionPoint.x = (edge.endPoint.x + edge.startPoint.x)/2;
		bisectionPoint.y = (edge.endPoint.y + edge.startPoint.y)/2;

		Normal.b = bisectionPoint.y - (Normal.slope * bisectionPoint.x);
	}
	
	return Normal;
}

bool LinesIntersect (Line line1 , Line line2)
{
	if(line1.slope == line2.slope)
		return false;
	else
		return true;
}

Vertex FindPointOfIntersect(Line line1 , Line line2)
{
	Vertex intersectionPoint;
	if(line1.slope == 0 && line1.x == -100000000)
	{
		intersectionPoint.y = line1.y;
		intersectionPoint.x = (intersectionPoint.y - line2.b) / line2.slope;
	}
	else if(line1.slope == 0 && line1.y == -100000000)
	{
		intersectionPoint.x = line1.x;
		intersectionPoint.y = (line2.slope * intersectionPoint.x) + line2.b;
	}
	else if(line2.slope == 0 && line2.x == -100000000)
	{
		intersectionPoint.y = line2.y;
		intersectionPoint.x = (intersectionPoint.y - line1.b) / line1.slope;
	}
	else if(line2.slope == 0 && line2.y == -100000000)
	{
		intersectionPoint.x = line2.x;
		intersectionPoint.y = (line1.slope * intersectionPoint.x) + line1.b;
	}
	else
	{
		intersectionPoint.x = (line1.b - line2.b) / (line2.slope - line1.slope);
		intersectionPoint.y = (line1.slope * intersectionPoint.x) + line1.b;
	}
	return intersectionPoint;
}

bool CanBeExtrime (Bisector Voronoi[] ,int voronoiSize, Vertex selectedVertex , Vertex secondVertex)
{
	Line halfLine = GetLineEquation(selectedVertex , secondVertex);
	for(int i=0;i<voronoiSize;i++)
	{
		Line l = GetLineEquation(Voronoi[i].site1 , Voronoi[i].site2);
		if(Voronoi[i].site1 != selectedVertex && Voronoi[i].site2 != selectedVertex && LinesIntersect(halfLine , l))
		{
			Vertex intersection = FindPointOfIntersect(halfLine , l);
			if((intersection.y > Voronoi[i].site1.y && intersection.y < Voronoi[i].site2.y) ||
				(intersection.y > Voronoi[i].site2.y && intersection.y < Voronoi[i].site1.y))
			return false;
		}
	}
	return true;
}

void ConstructChain(Bisector F_Voronoi[] , Bisector S_Voronoi[] , int &F_Voronoi_Size , int &S_Voronoi_Size ,
				  Vertex F_Voronoi_HeighestVertex , Vertex F_Voronoi_LowestVertex ,
				  Vertex S_Voronoi_HeighestVertex , Vertex S_Voronoi_LowestVertex)
{
	Line F_HalfLineNormal , S_HalfLineNormal , currentNormal;
	Edge F_Edge , currentEdge;
	F_Edge.startPoint = F_Voronoi_HeighestVertex;
	F_Edge.endPoint = S_Voronoi_HeighestVertex;
	F_Edge.line = GetLineEquation(F_Voronoi_HeighestVertex , S_Voronoi_HeighestVertex);
	F_HalfLineNormal =  GetLineNormal(F_Edge);

	Edge S_Edge;
	S_Edge.startPoint = F_Voronoi_LowestVertex;
	S_Edge.endPoint = S_Voronoi_LowestVertex;
	S_Edge.line = GetLineEquation(F_Voronoi_LowestVertex , S_Voronoi_LowestVertex);
	S_HalfLineNormal =  GetLineNormal(S_Edge);

	
	
	currentNormal = F_HalfLineNormal;
	currentEdge = F_Edge;

	Vertex F_Voronoi_lastVertex  , S_Voronoi_lastVertex , newVertex , F_Voronoi_lastIntersection , S_Voronoi_lastIntersection;
	bool notS_HalfLineNormal = true;
	Vertex lastIntersection = FindPointOfIntersect(currentNormal , F_Edge.line);
	lastIntersection.y += 5;
	cout<<"last intersection =  (" <<lastIntersection.x <<" , "<<lastIntersection.y<<")\n";
	////////////////////////////// find which Voronoi line first intersects the normal on the half line
	/////// first search the F_voronoi 
	while(notS_HalfLineNormal == true)
	{
		Vertex F_Voronoi_lastVertex;
		Vertex S_Voronoi_lastVertex;
		F_Voronoi_lastIntersection.y = -100000;
		for(int i=0;i<F_Voronoi_Size;i++)
		{
			if(F_Voronoi[i].site1 == currentEdge.startPoint && F_Voronoi[i].site2.y <= F_Voronoi[i].site1.y && LinesIntersect(currentNormal , F_Voronoi[i].line)) 
			{
				newVertex = FindPointOfIntersect(currentNormal , F_Voronoi[i].line);
				cout<<"("<<F_Voronoi[i].site1.x<<" , "<<F_Voronoi[i].site1.y<<") intersects "<<"("<<F_Voronoi[i].site2.x<<" , "<<F_Voronoi[i].site2.y<<") in "<<"("<<newVertex.x<<" , "<<newVertex.y<<")\n";
				//if(newVertex.y > F_Voronoi_lastIntersection.y && newVertex.y < F_Voronoi[i].site1.y)
				if(F_Voronoi[i].site2.x > F_Voronoi_lastVertex.x /*&& (newVertex.y <= F_Voronoi[i].site1.y)*/ && (newVertex.y <= lastIntersection.y))
				{
					F_Voronoi_lastIntersection = newVertex;
					F_Voronoi_lastVertex = F_Voronoi[i].site2;
				}
			}
			else if(F_Voronoi[i].site2 == currentEdge.startPoint && F_Voronoi[i].site1.y <= F_Voronoi[i].site2.y && LinesIntersect(currentNormal , F_Voronoi[i].line))
			{
				newVertex = FindPointOfIntersect(currentNormal , F_Voronoi[i].line);
				cout<<"("<<F_Voronoi[i].site1.x<<" , "<<F_Voronoi[i].site1.y<<") intersects "<<"("<<F_Voronoi[i].site2.x<<" , "<<F_Voronoi[i].site2.y<<") in "<<"("<<newVertex.x<<" , "<<newVertex.y<<")\n";
				//if(newVertex.y > F_Voronoi_lastIntersection.y && newVertex.y < F_Voronoi[i].site2.y)
				if(F_Voronoi[i].site1.x > F_Voronoi_lastVertex.x /*&& (newVertex.y <= F_Voronoi[i].site2.y)*/ && (newVertex.y <= lastIntersection.y))
				{
					F_Voronoi_lastIntersection = newVertex;
					F_Voronoi_lastVertex = F_Voronoi[i].site1;
				}
			}
		}
		cout<<"F_Voronoi_lastVertex ("<<F_Voronoi_lastVertex.x<<" , "<<F_Voronoi_lastVertex.y<<")\n";
		////// second search the S_voronoi
		S_Voronoi_lastIntersection.y = -100000;
		for(int i=0;i<S_Voronoi_Size;i++)
		{
			if(S_Voronoi[i].site1 == currentEdge.endPoint && S_Voronoi[i].site2.y <= S_Voronoi[i].site1.y && LinesIntersect(currentNormal , S_Voronoi[i].line)) 
			{
				newVertex = FindPointOfIntersect(currentNormal , S_Voronoi[i].line);
				cout<<"("<<S_Voronoi[i].site1.x<<" , "<<S_Voronoi[i].site1.y<<") intersects "<<"("<<S_Voronoi[i].site2.x<<" , "<<S_Voronoi[i].site2.y<<") in "<<"("<<newVertex.x<<" , "<<newVertex.y<<")\n";
				//if(newVertex.y > S_Voronoi_lastIntersection.y && newVertex.y < S_Voronoi[i].site1.y)
				if(S_Voronoi[i].site2.x > S_Voronoi_lastVertex.x /*&& (newVertex.y <= S_Voronoi[i].site1.y)*/ && (newVertex.y <= lastIntersection.y) )
				{
					S_Voronoi_lastIntersection = newVertex;
					S_Voronoi_lastVertex = S_Voronoi[i].site2;
				}
			}
			else if(S_Voronoi[i].site2 == currentEdge.endPoint && S_Voronoi[i].site1.y <= S_Voronoi[i].site2.y && LinesIntersect(currentNormal , S_Voronoi[i].line))
			{
				newVertex = FindPointOfIntersect(currentNormal , S_Voronoi[i].line);
				//if(newVertex.y > S_Voronoi_lastIntersection.y && newVertex.y < S_Voronoi[i].site2.y)
				if(S_Voronoi[i].site1.x > S_Voronoi_lastVertex.x /*&& (newVertex.y <= S_Voronoi[i].site2.y)*/ && (newVertex.y <= lastIntersection.y))
				{
					S_Voronoi_lastIntersection = newVertex;
					S_Voronoi_lastVertex = S_Voronoi[i].site1;
				}
			}
		}
		cout<<"S_Voronoi_lastVertex ("<<S_Voronoi_lastVertex.x<<" , "<<S_Voronoi_lastVertex.y<<")\n";

		cout<<"Point of intersect F = ("<<F_Voronoi_lastIntersection.x<<" , "<<F_Voronoi_lastIntersection.y<<")\n";
		cout<<"Point of intersect S = ("<<S_Voronoi_lastIntersection.x<<" , "<<S_Voronoi_lastIntersection.y<<")\n";

		/*if(F_Voronoi_lastVertex == S_Voronoi_lastVertex && F_Voronoi_lastVertex.y == 0 )
		{
			F_Voronoi_lastVertex = S_Edge.startPoint;
			S_Voronoi_lastVertex = S_Edge.endPoint;
		}*/
		 if (F_Voronoi_lastVertex.x == 0 && F_Voronoi_lastVertex.y == 0)
			F_Voronoi_lastVertex = currentEdge.startPoint;
		else if (S_Voronoi_lastVertex.x == 0 && S_Voronoi_lastVertex.y == 0)
			S_Voronoi_lastVertex = currentEdge.endPoint;
		else if(F_Voronoi_lastIntersection.y > S_Voronoi_lastIntersection.y)
		{
			S_Voronoi_lastVertex = currentEdge.endPoint;
		}
		else if(F_Voronoi_lastIntersection.y < S_Voronoi_lastIntersection.y)
		{
			F_Voronoi_lastVertex = currentEdge.startPoint;
		}
		cout<<"BUT NOW !!\n";
		cout<<"F_Voronoi_lastVertex ("<<F_Voronoi_lastVertex.x<<" , "<<F_Voronoi_lastVertex.y<<")\n";
		cout<<"S_Voronoi_lastVertex ("<<S_Voronoi_lastVertex.x<<" , "<<S_Voronoi_lastVertex.y<<")\n";
		Bisector newBisector;
		Edge edge;
		edge.startPoint = F_Voronoi_lastVertex;
		newBisector.site1 = F_Voronoi_lastVertex;
		edge.endPoint = S_Voronoi_lastVertex;
		newBisector.site2 = S_Voronoi_lastVertex;
		edge.line = GetLineEquation(F_Voronoi_lastVertex , S_Voronoi_lastVertex);
		newBisector.line =  GetLineNormal(edge);
		 lastIntersection = FindPointOfIntersect(newBisector.line , edge.line);
		 lastIntersection.y += 2;
		 cout<<"last intersection =  (" <<lastIntersection.x <<" , "<<lastIntersection.y<<")\n";
		F_Voronoi[F_Voronoi_Size] = newBisector;
		F_Voronoi_Size++;

		///// if the new line is the second half line then stop
		if(edge.line == S_Edge.line)
			notS_HalfLineNormal = false;

		currentNormal = newBisector.line;
		currentEdge.startPoint = F_Voronoi_lastVertex;
		currentEdge.endPoint = S_Voronoi_lastVertex;
	}

	F_Voronoi[F_Voronoi_Size].site1 = F_Edge.startPoint;
	F_Voronoi[F_Voronoi_Size].site2 = F_Edge.endPoint;
	F_Voronoi[F_Voronoi_Size].line = F_HalfLineNormal;
	F_Voronoi_Size++;
}

void Divide_And_Conquer (Vertex sites[] , int start , int numOfSites , Bisector F_Voronoi[] , Bisector S_Voronoi[] , int &F_Voronoi_Size , int &S_Voronoi_Size , 
						 Vertex &F_Voronoi_HeighestVertex , Vertex &F_Voronoi_LowestVertex , 
						 Vertex &S_Voronoi_HeighestVertex , Vertex &S_Voronoi_LowestVertex)
{
	
	if((numOfSites-start) > 3)
	{
		int halfSites = (numOfSites+start) / 2;
		Divide_And_Conquer(sites , start , halfSites , F_Voronoi , S_Voronoi , F_Voronoi_Size , S_Voronoi_Size , F_Voronoi_HeighestVertex ,
						   F_Voronoi_LowestVertex , S_Voronoi_HeighestVertex , S_Voronoi_LowestVertex);
		Divide_And_Conquer(sites , halfSites , numOfSites , F_Voronoi , S_Voronoi , F_Voronoi_Size , S_Voronoi_Size , F_Voronoi_HeighestVertex ,
						   F_Voronoi_LowestVertex , S_Voronoi_HeighestVertex , S_Voronoi_LowestVertex);
	}

	else
	{

		if(F_Voronoi_Size == 0)
		{
			if((numOfSites - start) % 2 == 0)
				F_Voronoi_Size = (numOfSites - start)-1;
			else
				F_Voronoi_Size = (numOfSites - start);
			for(int i = 0; i < F_Voronoi_Size; i++)
			{
				if(i == 2 && sites[i] == sites[i-1] && sites[i] == sites[i-2])
					break;
				if(F_Voronoi_Size == 1)
					F_Voronoi_Size++;
				F_Voronoi[i].site1 = sites[start + (i%F_Voronoi_Size)];
				F_Voronoi[i].site2 = sites[start + ((i+1)%F_Voronoi_Size)];

				Edge edge;
				edge.startPoint = F_Voronoi[i].site1;
				edge.endPoint = F_Voronoi[i].site2;
				edge.line = GetLineEquation(F_Voronoi[i].site1 , F_Voronoi[i].site2);
				F_Voronoi[i].line =  GetLineNormal(edge);
				cout<<"("<<F_Voronoi[i].site1.x<<" , "<<F_Voronoi[i].site1.y<<")   "<<"("<<F_Voronoi[i].site2.x<<" , "<<F_Voronoi[i].site2.y<<")   "<<"   b = "<<edge.line.b<<"    S = "<<edge.line.slope<<"    x = "<<edge.line.x<<"    y = "<<edge.line.y<<"    Nb = "<<F_Voronoi[i].line.b<<"  NS = "<<F_Voronoi[i].line.slope<<"    Nx = "<<F_Voronoi[i].line.x<<"    Ny = "<<F_Voronoi[i].line.y<<endl;

				if(F_Voronoi[i].site2.y > F_Voronoi[i].site1.y )
				{
					if(F_Voronoi[i].site1.y < F_Voronoi_LowestVertex.y)
						F_Voronoi_LowestVertex = F_Voronoi[i].site1;
					if(F_Voronoi[i].site2.y > F_Voronoi_HeighestVertex.y)
					F_Voronoi_HeighestVertex = F_Voronoi[i].site2;
				}
				else
				{
					if(F_Voronoi[i].site2.y < F_Voronoi_LowestVertex.y)
						F_Voronoi_LowestVertex = F_Voronoi[i].site2;
					if(F_Voronoi[i].site1.y > F_Voronoi_HeighestVertex.y)
						F_Voronoi_HeighestVertex = F_Voronoi[i].site1;
				}
				if(F_Voronoi_Size == 2)
				F_Voronoi_Size--;
			}
		}

		else
		{
			if(F_Voronoi_HeighestVertex.y < S_Voronoi_HeighestVertex.y)
				F_Voronoi_HeighestVertex = S_Voronoi_HeighestVertex;
			if(F_Voronoi_LowestVertex.y > S_Voronoi_LowestVertex.y)
				F_Voronoi_LowestVertex = S_Voronoi_LowestVertex;

			
			S_Voronoi_HeighestVertex.y = -100000;
			S_Voronoi_LowestVertex.y = 100000;
			if((numOfSites - start) % 2 == 0)
				S_Voronoi_Size = (numOfSites - start)-1;
			else
				S_Voronoi_Size = (numOfSites - start);
			S_Voronoi = new Bisector[100];
			//int Start = start - 1;
			for(int i = 0 ; i <S_Voronoi_Size; i++)
			{
				if(S_Voronoi_Size == 1)
					S_Voronoi_Size++;
				S_Voronoi[i].site1 = sites[start + (i%S_Voronoi_Size)];
				S_Voronoi[i].site2 = sites[start + ((i+1)%S_Voronoi_Size)];
				Edge edge;
				edge.startPoint = S_Voronoi[i].site1;
				edge.endPoint = S_Voronoi[i].site2;
				edge.line = GetLineEquation(S_Voronoi[i].site1 , S_Voronoi[i].site2);
				S_Voronoi[i].line =  GetLineNormal(edge);
				cout<<"("<<S_Voronoi[i].site1.x<<" , "<<S_Voronoi[i].site1.y<<")   "<<"("<<S_Voronoi[i].site2.x<<" , "<<S_Voronoi[i].site2.y<<")   "<<"   b = "<<edge.line.b<<"    S = "<<edge.line.slope<<"    Nb = "<<S_Voronoi[i].line.b<<"  NS = "<<S_Voronoi[i].line.slope<<endl;

				if(S_Voronoi[i].site2.y > S_Voronoi[i].site1.y )
				{
					if(S_Voronoi[i].site1.y < S_Voronoi_LowestVertex.y)
						S_Voronoi_LowestVertex = S_Voronoi[i].site1;
					if(S_Voronoi[i].site2.y > S_Voronoi_HeighestVertex.y)
						S_Voronoi_HeighestVertex = S_Voronoi[i].site2;
				}
				else
				{
					if(S_Voronoi[i].site2.y < S_Voronoi_LowestVertex.y)
						S_Voronoi_LowestVertex = S_Voronoi[i].site2;
					if(S_Voronoi[i].site1.y > S_Voronoi_HeighestVertex.y)
						S_Voronoi_HeighestVertex = S_Voronoi[i].site1;
				}
				if(S_Voronoi_Size == 2)
				S_Voronoi_Size--;
			}

			Vertex FH = F_Voronoi_HeighestVertex;
			Vertex FL = F_Voronoi_LowestVertex;
			while(CanBeExtrime(F_Voronoi , F_Voronoi_Size , FH , S_Voronoi_HeighestVertex) == false)
			{
				Vertex maxY;
				maxY.y = -10000000;
				Vertex minY;
				for(int i=0;i<F_Voronoi_Size;i++)
				{
					if( F_Voronoi[i].site1.y > maxY.y && F_Voronoi[i].site1.y < FH.y )
						maxY = F_Voronoi[i].site1;
					if( F_Voronoi[i].site2.y > maxY.y && F_Voronoi[i].site2.y < FH.y )
						maxY = F_Voronoi[i].site2;
				}
				FH = maxY;
			}

			while(CanBeExtrime(F_Voronoi , F_Voronoi_Size , FL , S_Voronoi_LowestVertex) == false)
			{
				Vertex minY;
				minY.y= 10000000;
				for(int i=0;i<F_Voronoi_Size;i++)
				{
					if( F_Voronoi[i].site1.y < minY.y && F_Voronoi[i].site1.y > FL.y )
						minY = F_Voronoi[i].site1;
					if( F_Voronoi[i].site2.y < minY.y && F_Voronoi[i].site2.y > FL.y )
						minY = F_Voronoi[i].site2;
				}
				FL = minY;

			}
			ConstructChain( F_Voronoi ,  S_Voronoi , F_Voronoi_Size , S_Voronoi_Size ,
				FH ,  FL ,
				S_Voronoi_HeighestVertex ,  S_Voronoi_LowestVertex);

			for(int i = 0; i < S_Voronoi_Size; i++)
			{
				F_Voronoi[F_Voronoi_Size] = S_Voronoi[i];
				F_Voronoi_Size++;
			}

			for(int i=0;i<F_Voronoi_Size;i++)
			{
				cout<<"Bisector between    ("<<F_Voronoi[i].site1.x<<" , "<<F_Voronoi[i].site1.y<<")		("<<F_Voronoi[i].site2.x<<" , "<<F_Voronoi[i].site2.y<<")\n";
			}
		}
	}
}



void main()
{
	Bisector* F_Voronoi = new Bisector[100];
	int F_Voronoi_Size = 0;
	Bisector* S_Voronoi = new Bisector[100];
	int S_Voronoi_Size = 0;

	Vertex F_Voronoi_HeighestVertex;
	F_Voronoi_HeighestVertex.y = -100000;
	Vertex F_Voronoi_LowestVertex;
	F_Voronoi_LowestVertex.y = 100000;
	Vertex S_Voronoi_HeighestVertex;
	S_Voronoi_HeighestVertex.y = -100000;
	Vertex S_Voronoi_LowestVertex;
	S_Voronoi_LowestVertex.y = 100000;

	Vertex sites[MAX_NUM_OF_VERTECIES];

	Vertex vertex;
	ifstream file("sites.txt");
	int numOfSites = 0;

	while(!file.eof())
	{
		file>>sites[numOfSites].x;
		file>>sites[numOfSites].y;
		numOfSites++;
	}
	file.close();
	QuickSort(0 , numOfSites-1 , sites);
	Divide_And_Conquer(sites , 0 , numOfSites , F_Voronoi , S_Voronoi , F_Voronoi_Size , S_Voronoi_Size ,
					   F_Voronoi_HeighestVertex , F_Voronoi_LowestVertex , S_Voronoi_HeighestVertex , 
					   S_Voronoi_LowestVertex);

	
	cout<<"F_V_SIZE = "<<F_Voronoi_Size<<endl;
}